package org.example.leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 40. 组合总和 II
 * 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的每个数字在每个组合中只能使用 一次 。
 * 注意：解集不能包含重复的组合。
 */
public class Code40 {
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtracking(candidates, target, 0);
        return res;
    }

    private void backtracking(int[] candidates, int target, int startIndex) {
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            if (candidates[i] > target) {
                break;
            }
            // 关键修正：跳过同一层级的重复元素
            // i > startIndex 表示不是当前层级的第一个元素
            // candidates[i] == candidates[i-1] 表示与前一个元素相同
            // 这种情况下跳过，避免产生重复组合
            if (i > startIndex && candidates[i] == candidates[i - 1]) {
                continue;
            }
            path.add(candidates[i]);
            backtracking(candidates, target - candidates[i], i + 1);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        Code40 solution = new Code40();

        // 测试用例1: candidates = [10,1,2,7,6,1,5], target = 8
        int[] candidates1 = {10, 1, 2, 7, 6, 1, 5};
        System.out.println("candidates = [10,1,2,7,6,1,5], target = 8");
        System.out.println("输出: " + solution.combinationSum2(candidates1, 8));
        solution.res.clear();
        solution.path.clear();

        // 测试用例2: candidates = [2,5,2,1,2], target = 5
        int[] candidates2 = {2, 5, 2, 1, 2};
        System.out.println("\ncandidates = [2,5,2,1,2], target = 5");
        System.out.println("输出: " + solution.combinationSum2(candidates2, 5));
        solution.res.clear();
        solution.path.clear();

        // 测试用例3: candidates = [1,1,1,1], target = 2
        int[] candidates3 = {1, 1, 1, 1};
        System.out.println("\ncandidates = [1,1,1,1], target = 2");
        System.out.println("输出: " + solution.combinationSum2(candidates3, 2));
        solution.res.clear();
        solution.path.clear();

        // 测试用例4: candidates = [1,2,3], target = 4
        int[] candidates4 = {1, 2, 3};
        System.out.println("\ncandidates = [1,2,3], target = 4");
        System.out.println("输出: " + solution.combinationSum2(candidates4, 4));
        solution.res.clear();
        solution.path.clear();

        // 测试用例5: candidates = [], target = 0
        int[] candidates5 = {};
        System.out.println("\ncandidates = [], target = 0");
        System.out.println("输出: " + solution.combinationSum2(candidates5, 0));
        solution.res.clear();
        solution.path.clear();

        // 测试用例6: candidates = [1,2], target = 0
        int[] candidates6 = {1, 2};
        System.out.println("\ncandidates = [1,2], target = 0");
        System.out.println("输出: " + solution.combinationSum2(candidates6, 0));
        solution.res.clear();
        solution.path.clear();
    }
}
